from random import *
from math import log
from functools import reduce
import operator


prime_table1000 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
                   59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
                   127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181,
                   191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251,
                   257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
                   331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397,
                   401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
                   467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557,
                   563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619,
                   631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
                   709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787,
                   797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
                   877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953,
                   967, 971, 977, 983, 991, 997]

def gent_prime_table(n):
    table = [2]
    for i in range(3,n,2):
        for p in table:
            if i%p == 0:
                break
        else:
            table.append(i)
    return table

def multiply_mod(a, b, mod):
    ans = 0
    res = a
    while b:
        if b&1:
            ans = (ans+res) % mod
        res = (res+res) % mod
        b >>= 1
    return ans

def power_mod(base, index, mod):
    if index > 0:
        s = power_mod(base, index//2, mod)
        s = s*s % mod
        return s*base % mod if index%2 else s
    else:
        return 1
        
def exgcd(a, b):
    if b > 0:
        r,x,y = exgcd(b, a%b)
        return r, y, x-a//b*y
    else:
        return a, 1, 0

def is_prime(n):
    '''Miller_Rabin'''
    if n%2==0 or n==1:
        return False
    if n < 1000:
        return n in prime_table1000
    #n=t*2^s
    t = n-1
    s = 0
    while not (t&1):
        s += 1
        t >>= 1
    for a in prime_table1000[:20]:
        b = power_mod(a,t,n)
        for i in range(s):
            bb = b*b%n
            if bb==1 and b!=1 and b!=n-1: #二次探测
                return False
            b = bb
        if b != 1: #Fermart小定理
            return False
    return True

def inverse(a, n):
    '''计算元素a在模n环中的逆元
要求(a,n)=1'''
    return exgcd(a, n)[1] % n

def crt(mod, rem):
    '''中国剩余定理(孙子定理)'''
    M = reduce(operator.__mul__, mod)
    ans = 0
    for m,r in zip(mod, rem):
        Mi = M//m
        ans += r*Mi*inverse(Mi, m)
    return ans % M


class RSA(object):
    def __init__(self, d, N=None):
        if N is None:
            while True:
                self.__p = randrange(2**18, 2**22)
                if is_prime(self.__p):
                    break
            while True:
                self.__q = randrange(2**18, 2**22)
                if is_prime(self.__q):
                    break
            self.N = self.__p * self.__q
            self.__phi_N = (self.__p-1) * (self.__q-1)
        else:
            self.N = N
            self.d = d
    
    def gent_key(self):
        while True:
            self.__e = randrange(self.__phi_N)
            if self.check_e():
                break
        self.d = inverse(self.__e, self.phi_N)
        
    def get_pub_key(self, d, N):
        return self.N, self.d
    
    def encrypt(self, x):
        return power_mod(x, self.__e, self.N)
    
    def decrypt(self, y):
        return power_mod(y, self.d, self.N)
        
        
rsa = RSA()
rsa.init()        